// 迭代器与容器

// ----------------------------------------------------
// C++容器（Container）
// C++标准模板库（STL）提供了多种容器类型，它们都是模板类，可以存储任意类型的数据。

// STL容器分类: 
// 1.顺序容器: 按照线性顺序存储元素
// std::vector: 动态数组，随机访问快，尾部插入删除快
// std::list: 双向链表，任意位置插入删除快，不支持随机访问
// std::deque: 双端队列，两端插入删除快，支持随机访问
// std::array（C++11）: 固定大小数组
// std::forward_list（C++11）: 单向链表

// 2.关联容器: 基于键值对的有序容器
// std::set: 有序集合，不允许重复元素
// std::multiset: 有序集合，允许重复元素
// std::map: 有序映射，键不可重复
// std::multimap: 有序映射，键可重复

// 3.无序关联容器（C++11）: 基于哈希表实现
// std::unordered_set: 无序集合，不允许重复元素
// std::unordered_multiset: 无序集合，允许重复元素
// std::unordered_map: 无序映射，键不可重复
// std::unordered_multimap: 无序映射，键可重复

// 4.容器适配器: 基于其他容器实现的接口
// std::stack: 栈，LIFO（后进先出）
// std::queue: 队列，FIFO（先进先出）
// std::priority_queue: 优先队列，最高优先级元素总是第一个出队

// -------------------------------------------------------------
// C++迭代器（Iterator）
// C++的迭代器是一种抽象的设计概念，提供了一种统一的方式来访问容器中的元素。

// C++迭代器分类（按功能递增）: 
// 1.输入迭代器（Input Iterator）: 
只读，单向，单次遍历
支持操作: ++、*（读取）、==、!=
例如: std::istream_iterator

// 2.输出迭代器（Output Iterator）: 
只写，单向，单次遍历
支持操作: ++、*（写入）
例如: std::ostream_iterator

// 3.前向迭代器（Forward Iterator）: 
可读写，单向，多次遍历
支持输入迭代器的所有操作
例如: std::forward_list::iterator

// 4.双向迭代器（Bidirectional Iterator）: 
可读写，双向，多次遍历
支持前向迭代器的所有操作，加上--
例如: std::list::iterator、std::map::iterator

// 5.随机访问迭代器（Random Access Iterator）: 
可读写，随机访问，多次遍历
// 支持双向迭代器的所有操作，加上+、-、+=、-=、[]、<、>、<=、>=
例如: std::vector::iterator、std::deque::iterator

// 6.连续迭代器（Contiguous Iterator，C++17）: 
// 随机访问迭代器的加强版，保证内存连续性
// 例如: std::vector::iterator、std::array::iterator、原生数组指针


// ---------------------------------------------------------
// 常用迭代器方法: 
// 每个STL容器通常提供以下迭代器方法：
begin()：返回指向容器第一个元素的迭代器
end()：返回指向容器尾部（最后一个元素之后）的迭代器
rbegin()：返回指向容器最后一个元素的反向迭代器
rend()：返回指向容器头部（第一个元素之前）的反向迭代器
C++11还引入了cbegin()、cend()、crbegin()、crend()等常量迭代器

// ---------------------------------------------------------
// C++中迭代器与容器的使用示例
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <algorithm>

int main() {
    // 向量容器及其迭代器
    std::vector<int> vec = {1, 2, 3, 4, 5};
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";  // 输出: 1 2 3 4 5
    }
    std::cout << std::endl;
    
    // C++11范围for循环（隐式使用迭代器）
    for (const auto& element : vec) {
        std::cout << element << " ";  // 输出: 1 2 3 4 5
    }
    std::cout << std::endl;
    
    // 列表容器及其迭代器
    std::list<int> lst = {10, 20, 30, 40};
    std::list<int>::iterator lst_it = lst.begin();
    ++lst_it;  // 移动到第二个元素
    lst.insert(lst_it, 15);  // 在第二个元素前插入15
    
    for (const auto& element : lst) {
        std::cout << element << " ";  // 输出: 10 15 20 30 40
    }
    std::cout << std::endl;
    
    // 映射容器及其迭代器
    std::map<std::string, int> age_map;
    age_map["Alice"] = 30;
    age_map["Bob"] = 25;
    age_map["Charlie"] = 35;
    
    for (std::map<std::string, int>::iterator it = age_map.begin(); it != age_map.end(); ++it) {
        std::cout << it->first << ": " << it->second << std::endl;
    }
    
    // 使用算法和迭代器
    std::vector<int> numbers = {5, 2, 8, 1, 9};
    std::sort(numbers.begin(), numbers.end());  // 排序
    
    // 使用反向迭代器
    for (std::vector<int>::reverse_iterator rit = numbers.rbegin(); rit != numbers.rend(); ++rit) {
        std::cout << *rit << " ";  // 输出: 9 8 5 2 1
    }
    std::cout << std::endl;
    
    return 0;
}
